import java.util.*;

/**
 * Created with Intellij JDEA
 * Description: O(1) 时间插入、删除和获取随机元素
 *   哈希表可以在O（1）的时间内做到 插入 和 删除，但是获取元素的O（1）是使用数组或者链表
 *   本题就需要 将 哈希表和ArrayList结合的方式进行 插入 删除和获取随机元素。
 * User:
 * Date:2022-04-13
 * Time:12:37
 */
public class 插入和删除和获取随机元素 {
    class RandomizedSet {
        List<Integer> list;
        Map<Integer,Integer> map;
        Random random;

        public RandomizedSet() {
            list = new ArrayList<Integer>();
            map = new HashMap<>();
            random = new Random();
        }

        public boolean insert(int val) {
            if (map.containsKey(val)){
                return false;
            }
            int index = list.size();
            list.add(val);
            map.put(val,index);
            return true;
        }

        public boolean remove(int val) {
            if (!map.containsKey(val)) {
                return false;
            }
            int end = list.get(list.size() - 1);
            int index = map.get(val);
            list.set(index,end);
            map.put(end,index);
            list.remove(list.size() - 1);
            map.remove(val);
            return true;
        }

        public int getRandom() {
            int randomIndex = random.nextInt(list.size());
            return list.get(randomIndex);
        }
    }

}
